Search for: All records

The \emph{p-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a p-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The problem is formalized as a multi-round game in which two players, a filler (who assigns work to tasks) and an emptier (who schedules tasks) compete. The emptier's goal is to minimize backlog, which is the maximum amount of outstanding work for any task. Recently, Kuszmaul and Westover (ITCS, 2021) proposed the \emph{variable-processor cup game}, which considers the same problem, except that the amount of resources available to the players (i.e., the number p of processors) fluctuates between rounds of the game. They showed that this seemingly small modification fundamentally changes the dynamics of the game: whereas the optimal backlog in the fixed p-processor game is Θ(logn), independent of p, the optimal backlog in the variable-processor game is Θ(n). The latter result was only known to apply to games with \emph{exponentially many} rounds, however, and it has remained an open question what the optimal tradeoff between time and backlog is for shorter games. This paper establishes a tight trade-off curve between time and backlog in the variable-processor cup game. Importantly, we prove that for a game consisting of t rounds, the optimal backlog is Θ(n) if and only if t≥Ω(n3). Our techniques also allow for us to resolve several other open questions concerning how the variable-processor cup game behaves in beyond-worst-case-analysis settings. 

In each step of the cup game on n cups, a filler distributes up to 1" water among the cups, and then an emptier removes 1 unit of water from a single cup. The emptier’s goal is to minimize the height of the fullest cup, also known as the backlog. The cup emptying game has found extensive applications to processor scheduling, network- switch buffer management, quality of service guarantees, and data- structure deamortization. The greedy emptying algorithm (i.e., always remove from the fullest cup) is known to achieve backlog O(log n) and to be the optimal deterministic algorithm. Randomized algorithms can do significantly better, achieving backlog O(log log n) with high probability, as long as " is not too small. In order to achieve these improvements, the known randomized algorithms require that the filler is an oblivious adversary, unaware of which cups the emptier chooses to empty out of at each step. Such randomized guarantees are known to be impossible against fully adaptive fillers. We show that, even when the filler is just slightly non- adaptive, randomized emptying algorithms can still guarantee a backlog of O(log log n). In particular, we give randomized ran- domized algorithms against an elevated adaptive filler, which is an adaptive filler that can see the precise fills of every cup containing more than 3 units of water, but not of the cups containing less than 3 units. 

First introduced in 1954, the linear-probing hash table is among the oldest data structures in computer science, and thanks to its unrivaled data locality, linear probing continues to be one of the fastest hash tables in practice. It is widely believed and taught, however, that linear probing should never be used at high load factors; this is because of an effect known as primary clustering which causes insertions at a load factor of 1 - 1/x to take expected time O(x2) (rather than the intuitive running time of ⇥(x)). The dangers of primary clustering, first discovered by Knuth in 1963, have now been taught to generations of computer scientists, and have influenced the design of some of the most widely used hash tables in production. We show that primary clustering is not the foregone conclusion that it is reputed to be. We demonstrate that seemingly small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions: if these design decisions are made correctly, then even if a hash table operates continuously at a load factor of 1 - (1/x), the expected amortized cost per insertion/deletion is O(x). This is because the tombstones left behind by deletions can actually cause an anti-clustering effect that combats primary clustering. Interestingly, these design decisions, despite their remarkable effects, have historically been viewed as simply implementation-level engineering choices. We also present a new variant of linear probing (which we call graveyard hashing) that completely eliminates primary clustering on any sequence of operations: if, when an operation is performed, the current load factor is 1 1/x for some x, then the expected cost of the operation is O(x). Thus we can achieve the data locality of traditional linear probing without any of the disadvantages of primary clustering. One corollary is that, in the external-memory model with a data blocks of size B, graveyard hashing offers the following remarkably strong guarantee: at any load factor 1 1/x satisfying x = o(B), graveyard hashing achieves 1 + o(1) expected block transfers per operation. In contrast, past external-memory hash tables have only been able to offer a 1 + o(1) guarantee when the block size B is at least O(x2). Our results come with actionable lessons for both theoreticians and practitioners, in particular, that well- designed use of tombstones can completely change the asymptotic landscape of how the linear probing behaves (and even in workloads without deletions).